package tianhao.luo.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 逆波兰表达式计算
 *
 * @author: tianhao.luo@hand-china.com 2021/6/16  9:46
 */
public class PolandNotation {

    /**
     * 计算逆波兰表达式(整数计算)
     * @param expression 表达式
     * @return 返回结果
     */
    public static int calculate(String expression){
        // 将表达式解析成单个元素,并放入list中
        // expression以空格区分元素
        String[] s = expression.trim().split(" ");
        Stack<String> suffixStack = new Stack<>();
        for (int i = 0; i < s.length; i++) {
            String temp = s[i];
            // 遇到数字将数字压入栈
            if (temp.matches("\\d+")){
                suffixStack.push(temp);
            }else {
                // 遇到运算符,弹出栈顶两个元素
                String pop1 = suffixStack.pop();
                String pop2 = suffixStack.pop();
                int num1 = Integer.parseInt(pop1);
                int num2 = Integer.parseInt(pop2);
                // 靠近栈底的元素pop2,位于计算表达式的前面
                // 减法或者除法都是pop2在前
                int res = 0;
                if (temp.equals("-")){
                    res = num2-num1;
                }else if (temp.equals("+")){
                    res = num2+num1;
                }else if (temp.equals("*")){
                    res = num2*num1;
                }else if (temp.equals("/")){
                    res = num2/num1;
                }else {
                    throw new RuntimeException(temp+" 计算符号不支持");
                }
                // 将计算结果入栈
                suffixStack.push(String.valueOf(res));
            }
        }
        // 最后栈内的元素就是结果
        return Integer.parseInt(suffixStack.pop());
    }


    /**
     * 中缀表达式转化为list
     * @param infixExpression 中缀表达式
     * @return list
     */
    public static List<String> infixExpressionToList(String infixExpression){
        // 处理其中所有的空格
        infixExpression = infixExpression.replace(" ","");
        // 定义索引开始扫描
        int index = 0;
        List<String> list = new ArrayList<>();
        String tempStr ="";
        while (index < infixExpression.length()){
            char temp;
            // 对于扫描到的元素,需要判断是否是运算符
            // 如果是运算符,则直接加入list
            // 如果是数字,需要判断下一位是否还是数字,如果是数字则进行拼接;否则将拼接好的字符串加入list
            // ascii码中,数字0==>ascii中48,数字9===>ascii中57
            if ((temp =infixExpression.charAt(index)) < 48 || (temp=infixExpression.charAt(index)) > 57){
                // char转String
                list.add(temp+"");
            }else {
                tempStr = tempStr + infixExpression.charAt(index);
                // 下一位是符号,则将拼接的字符串加入list
                // 本位已经是表达式最后一位了,则不需要判断
                if (index != infixExpression.length() -1){
                    if (infixExpression.charAt(index+1) < 48 || infixExpression.charAt(index+1) > 57){
                        list.add(tempStr);
                        // 重置
                        tempStr="";
                    }
                }else {
                    list.add(tempStr);
                    // 最后一位重置tempStr,可做也可不做
                    tempStr ="";
                }
            }
            index++;
        }
        return list;
    }


    /**
     * 中缀表达式list转后缀表达式list
     *
     * 思路:
     * 1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2
     * 2. 从左到右扫描中缀表达式
     * 3. 遇到数时，将其压入s2
     * 4. 遇到运算符时，比较它与s1栈顶运算符的优先级
     *    1. 如果s1为空，或栈顶运算符为“（”，则直接将此运算符入s1栈
     *    2. 否则，若它优先级比s1栈顶运算符的高，将它压入s1栈
     *    3. 否则，若它优先级低于或等于s1栈顶运算符，将s1栈顶的运算符弹出并压入到s2中,再次转到(4-1)与s1中新的栈顶运算符相比较
     * 5. 遇到括号时：
     *    1. 如果是左括号“（”，则直接压入s1
     *    2. 如果是右括号“）”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
     * 6. 继续扫描表达式中下一个元素，重复3-5步，直到扫描完毕
     * 7. 将s1中剩余的运算符依次弹出并压入s2
     * 8. 依次弹出s2中元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
     * @param infixExpressionList 中缀表达式list
     * @return 后缀表达式list
     */
    public static List<String> infixToSuffixExpressionList(List<String> infixExpressionList){
        // 上面思路中的s2栈,它的作用就是作为转化结果的临时存储,并没有pop操作,所以我们可以用返回结果list代替
        List<String> list = new ArrayList<>();
        Stack<String> s1 = new Stack<>();

        for (String temp : infixExpressionList) {
            // 遇到数时，将其存入list
            if (temp.matches("\\d+")){
                list.add(temp);
            }else if (temp.equals("(")){
                // 如果是左括号“（”，则直接压入s1
                s1.push(temp);
            }else if (temp.equals(")")){
                // 如果是右括号“）”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
                while (!"(".equals(s1.peek())){
                    String pop = s1.pop();
                    list.add(pop);
                }
                // 丢弃s1中的左括号
                s1.pop();
            }else {
                // 遇到运算符时，比较它与s1栈顶运算符的优先级
                // 1. 如果s1为空，或栈顶运算符为“（”，则直接将此运算符入s1栈
                // 2. 否则，若它优先级比s1栈顶运算符的高，将它压入s1栈
                // 3. 否则，若它优先级低于或等于s1栈顶运算符，将s1栈顶的运算符弹出并压入到s2中,再次转到(4-1)与s1中新的栈顶运算符相比较

                // 可以直接判断temp的优先级低于或等于s1栈顶运算符;其他情况都是将temp压入s1栈,可以放入else中
                while (s1.size()!=0 && (priority(temp)<=priority(s1.peek()))){
                    String pop = s1.pop();
                    list.add(pop);
                }
                s1.push(temp);
            }
        }

        // 7. 将s1中剩余的运算符依次弹出并压入s2
        while (s1.size() !=0){
            String pop = s1.pop();
            list.add(pop);
        }


        //  8. 依次弹出s2中元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
        // 因为我们使用了list,list是先加入的先输出,恰好和栈的输出方式相反
        return list;
    }


    /**
     * 计算操作符的优先级
     *
     * @param operator 操作符
     * @return 优先级高返回1, 优先级低返回-1,符号不支持返回-1
     */
    public static int priority(String operator) {
        // 操作符 * - + / 都可以被java转化为char进行比较
        if ("*".equals(operator) || "/".equals(operator)) {
            return 1;
        } else if ("+".equals(operator) || "-".equals(operator)){
            return 0;
        }
        else {
            return -1;
        }
    }
}
